package Top100;

import Algorithm.backtrack.*;
import Algorithm.comprehensive.sumofSubSequence.LMS.*;
import Algorithm.comprehensive.sumofSubSequence.LMG.*;
import Algorithm.comprehensive.sumofSubSequence.LSG.*;
import Algorithm.comprehensive.sumofSubSequence.LSS.*;
import Algorithm.dynamic.*;
import DataStructure.arrayAndList.preSumAndDiffArray.PreSumArrayApply_ChangeMoney;
import DataStructure.stringOps.slidingWindow.ArrayPermutation_Sliding;
import DataStructure.tree.binaryTree.binaryTreeApply.BT_JumpLevelSum;

/**
 * @author liujun
 * @version 1.0
 * @date 2022/2/9
 * @author—Email ljfirst@mail.ustc.edu.cn
 * @blogURL https://blog.csdn.net/ljfirst/article/details/122782616?spm=1001.2014.3001.5502
 * @description 零钱交换专题
 * 有这样一个问题：给定不同面额的硬币 coins 和一个总金额 target，求出组成target金额的硬币序列。
 * <p>
 * 延伸出下列问题：
 * <p>
 * 1、零钱数组是否可以组成target表示的金额
 * 2、在1问题的基础上，凑出target表示金额所需要的最少零钱数量
 * 3、在2问题的基础上，进行排列组合
 * 3.1、组合问题和排列问题
 * 3.2、动态规划和回溯解法
 * 4、零钱数组每个数仅能用1次的基础上，是否还能凑出target表示金额
 * 5、在前4条的基础上，进行排列去重
 * 6、上述5个问题，零钱序列都可以随意组合，如果限制随意组合，仅能选取连续的钱币，那么是否还能凑出target表示金额
 * 7、上述7个问题是加和问题，如果是乘积呢？
 * 7.1、随意组合，凑出乘积等于target的组合
 * 7.2、连续组合，凑出乘积等于target的组合
 * 8、现在题目反过来，将target拆分为至少两个正整数的和，并使这些整数的乘积最大化
 * 9、总结一下上面的问题
 * 9.1、最大子段和(连续)   LSS：LargestSumOfSubSequence
 * 9.2、最大间隔和        LSG：LargestSumOfGap
 * 9.3、最大子段乘积(连续) LMS:LargestMultiOfSubSequence
 * 9.4、最大间隔乘积      LMG:LargestMultiOfGap
 * 10、如果给定的coins数组修改为二叉树：选取非相邻的二叉树节点进行组装，组装的最大值是多少？
 * 11、如果零钱数组加上数量限制数组，即每个零钱有一个限定使用的最大值，那么是否还能凑出target
 */
public interface ChangeMoney {

    /*
       总结：上述问题的考虑角度主要为：
       1、重复的数字：给定数组中是否包含重复的数字，比如：重复：[1,1,2]、不重复[1,2,3,4]
       2、选取方式：连续、不一定连续、一定不连续【子序列和子串问题】
       3、计算方式：求和还是求积
       4、匹配方式：选取集合为最值 best 还是指定值 target
       5、输出方式：输出结果集合、还是集合的数量、能否凑出集合、集合中的最优解
       6、输出结果：集合是排列还是组合结果，排列是否去重，还是结果集合中的最优
          比如：[1,1,2] 只计算一次，是组合。
               [1,1,2]、[1,2、1]、[2,1,1] 计算三次是排列
               [1,1,2] 不重复计算是排列去重

       常见做法：
       1、求连续和为最优解一般是 最大字段和，求连续和为指定值一般是 前缀和，不一定连续的情况考虑使用背包
       2、针对(5)输出结果，获取集合类最方便的是回溯，求最值问题一般是DP
       3、针对(2)选取方式和(6)输出结果，考虑加锁
       4、补充：回溯算法，递归的for循环中，i从0开始，是排列问题，从上次的深度depth开始，是组合问题，排列去重考虑加锁
     */

    default void ChangeMoney() {
        /*
           1、零钱数组【是否】可以组成target表示的金额
           1.1、数组可以   无限重复的选择
           1.2、数组不可以 无限重复的选择【演变成背包问题】
         */
        CombinationNum_BackTrack cn = new CombinationNum_BackTrack();                     // 数组可以   无限重复的选择
        CombinationNum_Dynamic tv = new CombinationNum_Dynamic();
        CombinationNum_NonRepeat_BackTrack cnr = new CombinationNum_NonRepeat_BackTrack();// 数组不可以 无限重复的选择
        CombinationNum_NonRepeat_Dynamic cnd = new CombinationNum_NonRepeat_Dynamic(); //undo

        // 2、在1问题的基础上，凑出target表示金额所需要的【最少】零钱数量
        ChangeMoney_Least_BackTrack cm = new ChangeMoney_Least_BackTrack(); // 同 CombinationNum_BackTrack
        ChangeMoney_Least_Dynamic cd = new ChangeMoney_Least_Dynamic();

        /*
           3、在2问题的基础上，对凑出target表示金额的【所有】结果，进行排列组合
           3.1、组合问题和排列问题
           3.2、动态规划和回溯解法
           注意：排列和组合的问题
           1、体现在Dynamic上是两层for循环，具体见 ChangeMoneyPermutation_Dynamic 和 ChangeMoneyCombination_Dynamic
           2、体现在BackTrack上是内层for的起始值，具体见 ChangeMoneyPermutation_BackTrack 和 ChangeMoneyCombination_BackTrack
         */
        ChangeMoneyPermutation_Dynamic cpd = new ChangeMoneyPermutation_Dynamic();
        ChangeMoneyCombination_Dynamic ccd = new ChangeMoneyCombination_Dynamic();
        ChangeMoneyPermutation_BackTrack cpb = new ChangeMoneyPermutation_BackTrack();
        ChangeMoneyCombination_BackTrack ccb = new ChangeMoneyCombination_BackTrack();

        // 4、零钱数组每个数仅能用1次的基础上，是否还能凑出target表示金额
        // 见1.2

        // 5、在前4条的基础上，当数组中存在重复的数时，进行排列"去重"【排列、组合、组合去重】
        ArrayCombination ac = new ArrayCombination();                            // 数组 全排列【全排列去重问题】【通过访问标记去重】
        ArrayCombination_WithMap acm = new ArrayCombination_WithMap();           // 数组 全排列【全排列去重问题】【通过map去重】
        ArrayCombination_WithMapArray acma = new ArrayCombination_WithMapArray();// 数组 全排列【全排列去重问题】【通过mapArray去重】
        ArrayCombination_SingleLock acs = new ArrayCombination_SingleLock();

        /* 6、上述5个问题，零钱序列都可以随意组合，
           6.1、如果限制随意组合，仅能选取连续的钱币，那么是否还能凑出target表示金额
           6.2、如果限制随意组合，仅能选取间隔的钱币，那么是否还能凑出target表示金额
        */
        PreSumArrayApply_ChangeMoney cc = new PreSumArrayApply_ChangeMoney();  // 前缀和--选取连续的钱币
        ChangeMoney_SumGap_BackTrack csgb = new ChangeMoney_SumGap_BackTrack();// 回溯---选取间隔的钱币

        /* 7、上述7个问题是加和问题，如果是乘积呢？
           7.1、随意组合，凑出乘积等于target的组合
           7.2、连续组合，凑出乘积等于target的组合
        */
        ChangeMoney_BackTrack clmg = new ChangeMoney_BackTrack();    //随意组合
        ArrayPermutation_Sliding as = new ArrayPermutation_Sliding();//连续组合

        // 8、现在题目反过来，将 target 拆分为至少两个正整数的和，并使这些整数的乘积最大化
        NumReduceMaxMulti rm = new NumReduceMaxMulti();
        NumReduceMaxMulti_Math rmm = new NumReduceMaxMulti_Math();

        /* 9、总结一下上面的问题
           9.1、最大子段和(连续)   LSS：LargestSumOfSubSequence
           9.2、最大间隔和        LSG：LargestSumOfGap
           9.3、最大子段乘积(连续) LMS:LargestMultiOfSubSequence
           9.4、最大间隔乘积      LMG:LargestMultiOfGap
        */
        LSS lss = new LSS_Dynamic();
        LSG lsg = new LSG_Dynamic();
        LMS lms = new LMS_Dynamic();
        LMG lmg = new LMG_Dynamic();

        // 10、如果给定的coins数组修改为二叉树：选取非相邻的二叉树节点进行组装，组装的最大值是多少？
        BT_JumpLevelSum btjs = new BT_JumpLevelSum();

        // 11、如果零钱数组加上数量限制数组，即每个零钱有一个限定使用的最大值，那么是否还能凑出target
        ChangeMoney_WithLimit_BackTrack cw = new ChangeMoney_WithLimit_BackTrack();
    }
}
